package com.lei.sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public void sort(int s[], int l, int r){
        if (l < r)
        {
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                // 从右向左找第一个小于等于x的位置
                while(i < j &&  x <= s[j]) {
                    j--;
                }
                if(i < j){
                    s[i++] = s[j];
                }
                // 从左向右找第一个大于等于x的位置
                while(i < j && x >= s[j]) {
                    i++;
                }
                if(i < j){
                    s[j--] = s[i];
                }
            }
            s[i] = x;
            // 递归调用
            sort(s, l, i - 1);
            sort(s, i + 1, r);
        }
    }

    public static void main(String[] args) {
        int[]arr = {6,2,1,10,3,5,8,7};
        int l = 0;
        int r = arr.length-1;
        QuickSort quickSsort = new QuickSort();
        System.out.println("original array:"+Arrays.toString(arr));
        quickSsort.sort(arr,l,r);
        System.out.println("\tsort array:"+Arrays.toString(arr));
    }
}
